#define _CRT_SECURE_NO_WARNINGS 1

/*
 * 线性表：n个具有相同特性的数据 的有限序列
 * 常见的线性表有
 * 顺序表、链表、栈、队列、字符串等等
 *
 * 线性表在逻辑上是线性的，在物理结构上不一定。
 * 在物理结构上，线性表常以数组或链式结构的形式存储
 *
 *
 * 顺序表
 * 存储单元的物理地址连续 且 数据依次存储 的线性结构。
 * 一般情况下用数组实现，
 * 或者可以说顺序表就是数组。
 * 在数组的基础上，还要求数据从头开始连续存储
 */

#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>

// #define N 1000
// typedef int elemType;
//
////静态顺序表
// typedef struct SeqList
//{
//     elemType a[N];
//     int size;   //表示数组中存储了多少个数据
// }SL;
//
////接口函数
// void SLInit(SL* ps);
// void SLPushBack(SL* ps, elemType x);
// void SLPopBack(SL* ps);
// void SLPushFront(SL* ps, elemType x);
// void SLPopFront(SL* ps);
//// ...

/*
 * 静态顺序表的不足之处：
 * 表的容量固定不能改变。
 * 若用不完则太浪费，而数据多又怕不够用
 *
 * 动态顺序表弥补了这一点，
 * C++STL 容器中的 vector 采用的就是该数据结构。
 */

typedef int elemType;

// 动态顺序表
typedef struct SeqList
{
    elemType *arr;
    int size;     // 表示数组中存储了多少个数据
    int capacity; // 表示数组的容量
} SL;

// 接口函数
// ctor 和 dtor
void SLInit(SL *ps);
void SLDestroy(SL *ps);
// 判空
int IsEmpty(SL *ps); // 顺序表为空返回 1，否则返回 0
// 增
void SLPushBack(SL *ps, elemType x);        // 尾插
void SLPushFront(SL *ps, elemType x);       // 头插：C++11STL 不支持，太慢
void SLInsert(SL *ps, int pos, elemType x); // 在指定位置 pos 前添加数据
// 删
void SLPopBack(SL *ps);        // 尾删
void SLPopFront(SL *ps);       // 头删：C++11STL 不支持。
void SLErase(SL *ps, int pos); // 删除指定位置 pos 的数据
// 查
/**
 * 查索引 & 查值
 *
 * FindByValue
 * 找到返回索引，找不到返回-1。
 * 有多个相同元素则只返回第一个。
 *
 * FindByIndex
 * 使用下标运算符即可。
 */
int SLFindByValue(SL *ps, elemType x);
// elemType SLFindByIndex(SL *ps, int pos);

// 逆序
void Reverse(SL *ps);
// 输出（用户可自定义）
void SLPrint(SL *ps); // 最多输出前 10 个元素